//
// Created by Administrator on 2021/11/12.
//

#include <cstdio>
#include <cstdlib>

#define MaxSize 100//定义队列中元素的最大个数
#define ElemType int
/*链式队列结点*/
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
    int length;//记录链表长度
} LinkNode;

/*链式队列
 * 单独定义，避免指针每次从头开始寻找
 * 头指针=头结点
 * 尾指针=尾结点*/
typedef struct {
    LinkNode *front, *rear;//队列的队头和队尾指针
} LinkQueue;

/*初始化队列(带头结点)*/
void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));//初始时front;rear都指向头结点
    Q.front->next = NULL;
}

//初始化队列(不带头结点)
void InitQueue_WithoutHead(LinkQueue &Q) {
//初始时front、rear 都指向NULL
    Q.front = NULL;
    Q.rear = NULL;
}


void TestLinkQueue() {
    LinkQueue Q;//声明一个队列
    InitQueue(Q);//初始化队列
// ...后续操作...
}

/*判断队列是否为空*/
bool IsEmpty(LinkQueue Q) {
    return Q.front == Q.rear;//注意判空条件
}

/*判断队列是否为空(不带头结点)
 * 925*/
bool IsEmpty_WithoutHead(LinkQueue Q) {
    return Q.front == NULL;//注意判空条件
}

/*新元素入队(带头结点)
 * 在链尾加入新节点*/
void EnQueue(LinkQueue &Q, ElemType x) {
    LinkNode *S = (LinkNode *) malloc(sizeof(LinkNode));//创造新节点
    S->data = x;//赋值
    S->next = NULL;//新节点连到主链
    Q.rear->next = S;//新结点插入到rear之后.
    Q.rear = S;//修改表尾指针（新节点成为尾结点）
}

/*新元素入队(不带头结点)
 * 在链尾加入新节点*/
void EnQueue_WithoutHead(LinkQueue &Q, ElemType x) {
    LinkNode *S = (LinkNode *) malloc(sizeof(LinkNode));
    S->data = x;
    S->next = NULL;
    if (Q.front == NULL) {
        //在空队列中插入第一个元素
        Q.front = S;//修改队头队尾指针(首次：新节点成为头结点)
        Q.rear = S;//新节点成为尾结点
    } else {
        Q.rear->next = S;//新结点插入到rear结点之后
        Q.rear = S;//修改rear 指针（新节点成为尾结点）
    }
}

/*队头元素出队(带头结点)
 * 在链头删除旧结点*/
bool DeQueue(LinkQueue &Q, ElemType &x) {
    if (Q.front == Q.rear) {
        return false;//空队
    }
    LinkNode *p = Q.front->next;//找到第一个元素
    x = p->data;//用变量x返回队头元素
    Q.front->next = p->next; //修改头结点的next=第一个节点的next=第二个结点
    if (Q.rear == p) {
        //此次是最后一个结点出队
        Q.rear = Q.front; //修改rear指针
    }
    free(p);//释放结点空间
    return true;
}

/*队头元素出队(不带头结点)*/
bool DeQueue_WithoutHead(LinkQueue &Q, ElemType &x) {
    if (Q.front == NULL) {
        return false; //空队
    }
    LinkNode *p = Q.front;//p指向此次出队的结点（找到第一个节点）
    x = p->data;//用变量x返回队头元素
    Q.front = p->next;//修改front 指针（头指针指向第二个节点）
    if (Q.rear == p) {
        //此次是最后一个结点出队
        Q.front = NULL;//front指向NULL
        Q.rear = NULL;//rear指向NULL
    }
    free(p);//释放结点空间
    return true;
}